洛谷题解 CF1760G 【SlavicG's Favorite Problem】

发表于 | 阅读次数：
本文字数： 3.4k | 阅读时长 ≈ 3 分钟

题目大意

给出起点、终点以及树的边权，判断是否存在一条路径使得从起点到终点经过的边的边权异或值为0，允许从任一点跳跃至除终点外的任一点一次

解题思路

异或的一个重要性质: $a \ xor \ a = 0$

首先考虑不跳跃的情况：

即找到一条从起点到终点的路径使得各边边权异或值为0

直接dfs即可

再考虑跳跃的情况：

假设一条从起点出发的路径各边边权异或值为 $x$

一条从终点出发的路径各边边权异或值为 $y$

若存在 $x=y$ 则存在满足题意的路径

设起点为 $S$ ，终点为 $T$

分别以 $S,T$ 为起点dfs记录到达任一点所有可能路径的各边边权的异或值（这里可以直接用set维护异或值）

若两种dfs中存在相同的异或值，则存在满足题目要求的路径

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;

struct edge
{
    long long v, w;
};

struct node
{
    long long u, v, w;
} num[100010];

vector<edge> G[100010];
set<long long> se;
set<long long>::iterator iter;

long long tl, t, n, m, s;
bool pd[100010], pl;

long long read()
{
    char c = getchar();
    long long k = 0;
    while (c < '0' || c > '9')
    {
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - 48;
        c = getchar();
    }
    return k;
}

bool cmp(node x, node y)
{
    return x.w < y.w;
};

void dfs(long long p, long long ws, int mods) // mods=0 第一种情况 mods=2 第二种情况
{
    if (pl)
    {
        return;
    }

    if (p == t && mods == 0) // 存在直达终点的合法路径
    {
        if (ws == 0 && !pl)
        {
            printf("YES\n");
            pl = true;
        }
        return;
    }
    if (p != t && mods == 0)
    {
        se.insert(ws);
    }
    for (long long i = 0; i < G[p].size(); ++i)
    {
        long long V = G[p][i].v, W = G[p][i].w;
        if (pl)
        {
            return;
        }
        if (!pd[V])
        {
            pd[V] = true;
            if (mods == 1)
            {
                iter = se.find(ws ^ W);
                if (iter != se.end() && !pl) // 存在跳跃后能到达终点的路径
                {
                    printf("YES\n");
                    pl = true;
                    return;
                }
            }
            dfs(G[p][i].v, ws ^ W, mods);
        }
    }
}

int main()
{
    scanf("%lld", &tl);
    while (tl--)
    {
        memset(pd, 0, sizeof(pd));
        memset(G, 0, sizeof(G));
        se.clear();
        n = read();
        s = read();
        t = read();
        pl = false;
        for (long long a = 1; a <= n - 1; ++a)
        {
            edge tmp;
            num[a].u = read();
            num[a].v = read();
            num[a].w = read();
            tmp.v = num[a].v;
            tmp.w = num[a].w;
            G[num[a].u].push_back(tmp);
            tmp.v = num[a].u;
            G[num[a].v].push_back(tmp);
        }
        pd[s] = true;
        dfs(s, 0, 0);
        if (pl) // 若存在
        {
            continue;
        }
        memset(pd, 0, sizeof(pd));
        if (!pl) //若不存在
        {
            pd[t] = true;
            dfs(t, 0, 1);
        }
        if (!pl) // 若不存在
        {
            printf("NO\n");
            continue;
        }
    }
    return 0;
}

题目详见：https://www.luogu.com.cn/problem/CF1760G